Used as: Division One - Level Three:
Value | 1000 |
Submission Rate | 7 / 576 (1.22%) |
Success Rate | 0 / 7 (0.00%) |
High Score | null for null points (NONE) |
Average Score | No correct submissions |
As a prerequisite to read this explanation, try solving the easier version, TheLuckyBasesDivTwo. Make sure you understand both of the approaches mentioned in its explanation because this larger problem can be seen as a combination of both.
Let us begin with the simplest case. When the base x is greater than n, the number will have the same numerical representation, a single digit equal to n. This time, n does not have to be only 4 or 7 to cause infinitely many lucky bases. If n is any lucky number, the result will be -1.
Continue with the simple approach that tries every base up to a higher bound and for each of the tried bases, finds if the base would be lucky. That approach does not change too much, but the lucky digits may not only be 4 or 7, but also 44, 47, 74,… 74747474, etc. We can still extract each digit and for each of them check if it is a lucky number. Then if all the digits are lucky numbers, the base is also lucky. The main issue here is that the old bound of SquareRoot(n) for the largest base to check is not low enough. This time, n <= 10^16. The square root is 10^8 and after factoring we get the additional O(log(n)*log(n)) factor that will be needed to extract digits and for each, to get if it is lucky. This approach will not run in time.
There is still hope. Remember that higher bases lead to smaller amounts of digits. So, if we processed 3-digit numbers separately as we processed 2-digit numbers separately in the easier version, then there will be a new upper bound for the simple approach. We want to know the maximum base x that will have four digits. Such a base will yield the following polynomial:
Max x: D3 * x3 + D2 * x2 + D1 * x1 + D0 = n
Where: (D3 >= 1 , D2,D1,D0 >= 0 ).
The maximum value of x is then cubic_root(n) or n1/3. The cubic root of n is at most 215443. So, if we try bases up to that number we will have all bases that yield more than three digits covered.
2 digits
The main difference is that this time, the only combinations are not just (4)(4), (4)(7), (7)(4) and (7)(7). For each pair of lucky numbers there may be a possible numeric representation of n in a lucky base. So, for example we may need to try (44)(7), (447447)(774), etc. The number of lucky numbers between 1 and 10^16 is: (216+215+…+22 = 131070) (Has this happened many times in this editorial?). So, if we do the naive estimation for the number of pairs: 131070*131070, it may appear that there are too many of them to try.
There are in fact, much fewer relevant pairs than 131070*131070. Let us call the pair (a, b). The polynomial will have to be:
a * x + b = n
Note that x must be greater than a and b. So that when we pick a value of a, then x is at least a+1. Which takes us to:
a * (a + 1) <= n
That is one condition. The following comes when we add the b term. Note that x will be at least a+1 and at least b+1. Let us call the minimum base u=max(a+1, b+1). Then we have:
a * u + b <= n
The number of pairs that follow these rules is actually much lower than it seems. 1047556 for n = 10^16. This number may be estimated through calculations and is in fact bounded as O(K * log(K)) where K is the number of lucky numbers smaller than N. That proof will be left as an exercise. But it is not necessary. During the match, it was possible to count the valid pairs manually with a program. Since the number of pairs is so low, we can use the solution that we also used in the easier version. That verifies if a given pair of digits is a possible representation of n.
3 digits
This is probably the hardest part. Three-digit numbers are triples (a, b, c) such that:
a * x2 + b * x + c = n
It may appear that there are many of such triples, but in reality, we can use the same thing we did in the case of two digits. First of all, x must be at least a+1. So, we can assume that a*a*a should not exceed n. When picking b, we have that the base is at least u = max(a+1,b+1), so (a*u*u + b*u) cannot exceed n. Finally, when picking c we have a new u = max(a+1, b+1, c+1) and (a*u*u + b*u + c) cannot exceed n either. Surprisingly, the total number of valid triples is smaller than the number of valid pairs. For n = 10^16 the number of triples is: 1006504. So, if for each of those triples we could verify if a base exists, we could count the bases that yield three digits and complete the problem.
We have the polynomial:
a * x2 + b * x + c = n
And we want to get a solution. It may be tempting to solve it as a quadratic equation:
a * x2 + b * x + (c-n) = 0
That is not possible through the normal means though. Because if we use the quadratic equation formula there is a moment at which : 4*a*(c - n) will overflow. Switching to doubles is also not a good option because we need to get integer, precise results. Arbitrary precision is probably going to be too slow (remember we are doing this for all 1006504 pairs and as a subtask of a problem that contains other run-time heavy subtasks). Then we could try binary search, like in the alternate approach for the easier version. Find the maximum x such that:
max x: a * x2 + b * x + c <= n
And then check if the polynomial is equal to n. If we pay attention to low level and we also make sure to bound the binary search correctly (i.e.: we do not need values higher than the square root of n, because if x was larger than sqrt(n), the number would have 2 digits, not 3), then it is possible to pass system tests using binary search. But since the editorial better not use very tight solutions, but solutions that you can implement with plenty of space for overhead, then we will need something better.
A work around comes from the fact that we picked values for a and b in two cycles and are trying values of c in increasing order. When picking the maximum value of x, a and b actually do most of the job because they are multiplied with the highest powers of x. Let us call the maximum x found for a triple (a, b, c) the “root” of a triple. Let us also define P(x) = a*x*x+b*x+c. Between two triples (a, b, c1) and (a, b, c2) such that c1 and c2 are consecutive (c2 > c1), there should be many similarities. In fact, the root of (a, b, c1) will always be greater than or equal to the root of (a, b, c2). Let us call x the root of (a, b, c1) and y the root of (a, b, c2):
max x: a * x2 + b * x + c1 <= n
max y: a * y2 + b * y + c2 <= n
We have that c2 is greater than c1, so it exceeds c1 by a positive number p:
max x: a * x2 + b * x + c1 <= n
max y: a * y2 + b * y + c1 + p <= n
max y: a * y2 + b * y + c1 <= n - p
---;
max x: Q(x) <= n
max y: Q(y) <= n - p
Note that the same formula is used both for the maximization of x and that of y. The difference is that y is more constrained. So, the maximum of y cannot exceed the maximum of x. This translates into the root of (a, b, c2) not being able to be larger than the root of (a, b, c1). When solving ( a, b, c2), the root of (a, b, c1) will already be known. Let us call this root last. If ( a * last * last + b * last + c2 < n ) then we can assume also that, if y is the root of the new pair then (a * y * y + b * y + c2) will be smaller than n, because of transitivity. By doing this check, we can avoid doing the binary search for many triples. In fact, it appears that when following this approach, you will only need to run binary search for two triples per each pair (a, b). This really lowers the execution time.
Once each triple can be verified, we can count the total number of lucky bases in which the representation of n has three digits.
Summary
* Split the problem in three parts: Number of lucky bases that yield 4 or more digits for n. Number of lucky bases with 2 digits and number of lucky bases with 3 digits.
* The 4 or more digits case can be done with simple bruteforce through the bases up to cubic_root(n).
* The 2 and 3 digits cases can be done by trying each possible combination of lucky digits. The number of pairs of digits and triples of digits that are relevant when doing these checks is actually around only one million. The three-digits case will need a binary search with optimizations to run in time.
Code
The following code requires 0.16 seconds in its worst case.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
public class TheLuckyBasesDivOne {
final long MAX = 10000000000000000 l;
// Calculates the necessary lucky numbers
// through backtracking.
//
long[] luckyNums;
int t;
void rec(long x) {
if (x <= MAX) {
if (x >= 1) {
luckyNums[t++] = x;
}
rec(x * 10 + 4);
rec(x * 10 + 7);
}
}
boolean isLucky(long x) {
return Arrays.binarySearch(luckyNums, x) >= 0;
}
long count4DorMore(long n) {
// counts all the bases x such that the base
// is lucky and n in that base has at least 4 digits
//
// (b*b*b will always be <= n)
//
long cnt = 0;
for (long b = 2; b <= n; b++) {
int cdigits = 0;
long x = n;
boolean luck = true;
while (x > 0) {
luck = luck && isLucky(x % b);
x /= b;
cdigits++;
}
if (cdigits <= 3) {
break;
}
if (luck) {
cnt++;
}
}
return cnt;
}
boolean canDoPair(long n, long a, long b) {
// Does a x exist such that:
// (x : a*x + b = n)
// x > a, x > b ?
long ax = n - b;
if (ax % a == 0) {
long x = ax / a;
return (x > a && x > b);
}
return false;
}
long count2D(long n) {
// counts all the bases x such that the base
// is lucky and n is a two digit number in that base
//
long r = 0;
for (long a: luckyNums) {
// Make sure (a*(a+1) <= n):
// The reason we check a > n/(a+1) instead of
// a*(a+1) > n is to avoid overflow.
//
if (a > n / (a + 1)) break;
for (long b: luckyNums) {
long u = Math.max(a, b) + 1;
// Make sure (a*u + $b <= n):
if (a > n / u) break;
if (a * u > n - b) break;
r += (canDoPair(n, a, b) ? 1 : 0);
}
}
return r;
}
//
long rootOfTriple(long a, long b, long c, long n) {
// Finds the root of a triple.
// That is, the maximum x such that:
// a*x*x + b*x + c <= n
//
// (simple binary search).
//
long lo = 0;
long hi = (long) Math.sqrt(n) + 1;
while (lo + 1 < hi) {
long ha = hi - (hi - lo) / 2;
boolean good = false;
if (a <= n / ha && a * ha <= n / ha) {
if (b <= n / ha && a * ha * ha <= n - b * ha) {
if (a * ha * ha + b * ha <= n - c) {
good = true;
}
}
}
if (good) {
lo = ha;
} else {
hi = ha;
}
}
return lo;
}
long count3D(long n) {
int TT = 0;
int r = 0;
for (long a: luckyNums) {
if (a > n / a) break;
if (a * a > n / a) break;
// Always crop. Make sure a*a*a <= n.
for (long b: luckyNums) {
long u = Math.max(a, b) + 1;
if (a > n / u) break;
if (a * u > n / u) break;
if (b * u > n) break;
if (a * u * u + b * u > n) break;
// (Make sure a*u*u + b*u <= n)
// ( where u = max(a,b)+1 )
long last = -1;
for (long c: luckyNums) {
long uu = Math.max(u, c + 1);
if (a > n / uu) break;
if (a * uu > n / uu) break;
if (b * uu > n) break;
if (a * uu * uu + b * uu > n) break;
if (a * uu * uu + b * uu + c > n) break;
// (Make sure a*u*u + b*u <= n)
// ( where uu = max(a,b,c)+1 )
TT++;
// If the the last value still is < n, skip.
if ((last != -1) && (a * last * last + b * last + c < n)) {
continue;
}
// Else do binary search again.
// All of this because the new "root" is guaranteed to
// be <= the old "root". Because the new c is larger
// than the previous c.
//
// (The root is just the maximum x such that
// a*x*x + b*x + c <= n)
//
long x = rootOfTriple(a, b, c, n);
if (a * x * x + b * x + c == n) {
r++;
}
last = x;
}
}
}
System.out.println("TT = " + TT);
return r;
}
public long find(long n) {
t = 0;
luckyNums = new long[1 << 17];
rec(0);
Arrays.sort(luckyNums, 0, t);
if (isLucky(n)) {
// Any base > n will be lucky.
return -1;
}
long res = 0;
res += count4DorMore(n);
res += count2D(n);
res += count3D(n);
return res;
}
}